package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 330. ��Ҫ�������飨�ɲο���ˢ���16�ڿ�Code03_MinPatches��
 * ����һ������������������� nums����һ��������n ����[1, n]������ѡȡ��������ֲ��䵽nums�У�ʹ��[1, n]�����ڵ��κ����ֶ�������nums��ĳ�������ֵĺ�����ʾ��
 * <p>
 * �뷵�� ��������Ҫ���������Ҫ��������ָ�����
 * <p>
 * ʾ��1:
 * <p>
 * ����: nums = [1,3], n = 6
 * ���: 1
 * ����:
 * ���� nums�����е����[1], [3], [1,3]�����Եó�1, 3, 4��
 * ����������ǽ�2��ӵ�nums �У���ϱ�Ϊ: [1], [2], [3], [1,3], [2,3], [1,2,3]��
 * ��Ϳ��Ա�ʾ����1, 2, 3, 4, 5, 6���ܹ�����[1, 6]���������е�����
 * ��������������Ҫ���һ�����֡�
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/patching-array
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/5/14:10:58
 */
public class Solution_330 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 5, 10};
        int n = 20;
        nums = new int[]{1, 3};
        n = 6;
        nums = new int[]{1, 2, 2};
        n = 5;
        nums = new int[]{1, 2, 31, 33};
        n = 2147483647;
        nums = new int[]{1, 7, 21, 31, 34, 37, 40, 43, 49, 87, 90, 92, 93, 98, 99};
        n = 12;
        System.out.println(minPatches(nums, n));

    }

    /**
     * eg:
     * nums={1, 5, 10},n=20;
     * L=0,����best=1=nums[0],range = 1;
     * L=1,����best=max(2*1,1+1)=2<nums[1]=5,��Ҫ�ֶ�����2��L����,range = 3,��ϣ��nums={1,2,5,10};
     * L=1,����best=max(2*2,3+1)=4<nums[1]=5,��Ҫ�ֶ�����4��L����,range = 7����ϣ��nums={1,2,4,5,10};
     * L=1,����best=max(2*4,7+1)=8>nums[1]=5,��������best=5��L+1,range = 7+5=12����ϣ��nums={1,2,4,5,10}������һ������һ��
     * L=2,����best=max(2*5,12+1)=13>nums[2]=10,��������best=10��L+1,range = 12+10=22>n=20�������˳�����
     * <p>
     * ps:
     * best=1->range=1
     * best=2->range=3
     * best=4->range=7
     * best=8->range=15
     * best=16->range=31
     * best=32->range=63
     * ���ɣ�
     * 1��bestÿ�ε���2����range����2*best-1
     * 2����һ�ε�best������һ��range+1
     * 3����һ�ε�range������һ��2*range+1
     *
     * @param nums
     * @param n
     * @return
     */
    public static int minPatches(int[] nums, int n) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(nums[i]);
        }
        int ans = 0;
        int L = 0;
        // ��ǰ�±�L�������ֵ
        long curBest = 0;
        // L=0..curBest,����1,2,...range
        long range = 0;// ����Խ�磬��Ҫ����
        while (L < N || range < n) {// ע�⣬�����������鵫��λ����n��������Ҫ������
            if (range >= n) {
                // �˳�����
                return ans;
            }
            curBest = Math.max(range + 1, 2 * curBest);
            long val = L < N ? nums[L] : curBest * 2;
            if (val <= curBest) {
                // ����
                range = range + val;
                curBest = val;
                L++;
            } else {
                range = range * 2 + 1;
                ans++;
            }
            // ����Խ��
            range = range >= Integer.MAX_VALUE ? Integer.MAX_VALUE : range;
        }
        return ans;
    }
}
